#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAX_POSTFIX_LEN 256

typedef int Status;

// ===== 运算符栈 (char) =====
typedef char SElemType_OPTR;
typedef struct
{
    SElemType_OPTR *base;
    SElemType_OPTR *top;
    int stacksize;
} SqStack_OPTR;

Status InitStack_OPTR(SqStack_OPTR *S)
{
    S->base = (SElemType_OPTR *)malloc(STACK_INIT_SIZE * sizeof(SElemType_OPTR));
    if (!S->base)
        exit(OVERFLOW);
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    return OK;
}

Status Push_OPTR(SqStack_OPTR *S, SElemType_OPTR e)
{
    if (S->top - S->base >= S->stacksize)
    {
        S->base = (SElemType_OPTR *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType_OPTR));
        if (!S->base)
            exit(OVERFLOW);
        S->top = S->base + S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *(S->top++) = e;
    return OK;
}

Status Pop_OPTR(SqStack_OPTR *S, SElemType_OPTR *e)
{
    if (S->top == S->base)
        return ERROR;
    *e = *--S->top;
    return OK;
}

SElemType_OPTR GetTop_OPTR(SqStack_OPTR S)
{
    if (S.top == S.base)
        return '\0'; // Return null char if empty
    return *(S.top - 1);
}

int StackEmpty_OPTR(SqStack_OPTR S)
{
    return S.top == S.base;
}

// ===== 操作数栈 (int) =====
typedef int SElemType_OPND;
typedef struct
{
    SElemType_OPND *base;
    SElemType_OPND *top;
    int stacksize;
} SqStack_OPND;

Status InitStack_OPND(SqStack_OPND *S)
{
    S->base = (SElemType_OPND *)malloc(STACK_INIT_SIZE * sizeof(SElemType_OPND));
    if (!S->base)
        exit(OVERFLOW);
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    return OK;
}

Status Push_OPND(SqStack_OPND *S, SElemType_OPND e)
{
    if (S->top - S->base >= S->stacksize)
    {
        S->base = (SElemType_OPND *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType_OPND));
        if (!S->base)
            exit(OVERFLOW);
        S->top = S->base + S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *(S->top++) = e;
    return OK;
}

Status Pop_OPND(SqStack_OPND *S, SElemType_OPND *e)
{
    if (S->top == S->base)
        return ERROR;
    *e = *--S->top;
    return OK;
}

// ===== 中缀转后缀 及 后缀求值 =====

// 获取运算符优先级
int get_precedence(char op)
{
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    return 0; // for parentheses
}

// 中缀转后缀
void infix_to_postfix(const char *infix, char *postfix)
{
    SqStack_OPTR op_stack;
    InitStack_OPTR(&op_stack);
    int i = 0, j = 0;

    while (infix[i] != '#' && infix[i] != '\0')
    {
        if (isdigit(infix[i]))
        {
            while (isdigit(infix[i]))
            {
                postfix[j++] = infix[i++];
            }
            postfix[j++] = ' '; // 用空格分隔数字
        }
        else if (infix[i] == '(')
        {
            Push_OPTR(&op_stack, infix[i]);
            i++;
        }
        else if (infix[i] == ')')
        {
            char op;
            while (!StackEmpty_OPTR(op_stack) && GetTop_OPTR(op_stack) != '(')
            {
                Pop_OPTR(&op_stack, &op);
                postfix[j++] = op;
                postfix[j++] = ' ';
            }
            Pop_OPTR(&op_stack, &op); // Pop '('
            i++;
        }
        else
        { // Operator
            while (!StackEmpty_OPTR(op_stack) && get_precedence(GetTop_OPTR(op_stack)) >= get_precedence(infix[i]))
            {
                char op;
                Pop_OPTR(&op_stack, &op);
                postfix[j++] = op;
                postfix[j++] = ' ';
            }
            Push_OPTR(&op_stack, infix[i]);
            i++;
        }
    }

    while (!StackEmpty_OPTR(op_stack))
    {
        char op;
        Pop_OPTR(&op_stack, &op);
        postfix[j++] = op;
        postfix[j++] = ' ';
    }
    postfix[j] = '\0';
}

// 计算后缀表达式
int evaluate_postfix(const char *postfix)
{
    SqStack_OPND num_stack;
    InitStack_OPND(&num_stack);
    int i = 0;

    while (postfix[i] != '\0')
    {
        if (isdigit(postfix[i]))
        {
            int num = 0;
            while (isdigit(postfix[i]))
            {
                num = num * 10 + (postfix[i] - '0');
                i++;
            }
            Push_OPND(&num_stack, num);
        }
        else if (postfix[i] == ' ')
        {
            i++;
        }
        else
        { // Operator
            int a, b;
            Pop_OPND(&num_stack, &b);
            Pop_OPND(&num_stack, &a);
            switch (postfix[i])
            {
            case '+':
                Push_OPND(&num_stack, a + b);
                break;
            case '-':
                Push_OPND(&num_stack, a - b);
                break;
            case '*':
                Push_OPND(&num_stack, a * b);
                break;
            case '/':
                if (b == 0)
                {
                    printf("错误：除数为零！\n");
                    exit(ERROR);
                }
                Push_OPND(&num_stack, a / b);
                break;
            }
            i++;
        }
    }
    int result;
    Pop_OPND(&num_stack, &result);
    return result;
}

int main()
{
    char infix_exp[256];
    char postfix_exp[MAX_POSTFIX_LEN * 2]; // *2 for spaces

    printf("方案二：中缀表达式转后缀表达式求值\n");
    printf("======================================\n");
    printf("请输入一个以'#'结尾的算术表达式 (例如: 12+(100-20)/4*2# ):\n");
    scanf("%s", infix_exp);

    infix_to_postfix(infix_exp, postfix_exp);
    printf("\n转换后的后缀表达式 (逆波兰式) 为: %s\n", postfix_exp);

    int result = evaluate_postfix(postfix_exp);
    printf("计算结果是: %d\n\n", result);

    return 0;
}